<template>
    <div class="demo-collapse">
        <el-collapse v-model="activeNames" @change="handleChange">
            <el-collapse-item title="解题思路" name="thinking">
                <div>
                    <div>
                        设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ,则：
                    </div>
                    <div>
                        &nbsp;&nbsp;&nbsp;(1)若xm=yn,则zk=xm=yn,且z1,z2,…, zk-1是否为x1,x2,…,xm-1和y1,y2,…,yn-1的最长公共子序列.
                    </div>
                    <div>
                        &nbsp;&nbsp;&nbsp;(2)若xm≠yn且zk≠xm,则Z是x1,x2,…,xm-1和Y的最长公共子序列。
                    </div>
                    <div>
                        &nbsp;&nbsp;&nbsp;(3)若xm≠yn且zk≠yn,则Z是X和y1,y2,…,yn-1的最长公共子序列。
                    </div>
                    <div>
                        由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系.用c[i][j]记录序列和的最长公共子序列的长度。
                    </div>
                    <div>
                        其中,Xi={x1,x2,…,xi},Yj={y1,y2,…,yj}.当i=0或j=0时,空序列是Xi和Yj的最长公共子序列.故此时C[i][j]=0.其它情况下,
                        由最优子结构性质可建立递归关系如下:
                    </div>
                    <div>
                        <img class="image" src="../../../../../assets/最长公共子序列/LCSS公式.png">
                    </div>
                </div>
            </el-collapse-item>
            <el-collapse-item title="代码实现" name="code">
                <!-- <el-image style="width:100%" :src="url" :fit="fit" loading="lazy"></el-image> -->
                <div v-highlight>
                    <div>C/C++:</div>
                    <pre class="language-javascript">
                      <code>
                      #include &lt;iostream>

                      using namespace std;

                      /*
                      * 这里可以不定义长度，输入的字符串用string存储，然后利用string.c_str()来对字符串进行数组转化。 我这里为了方便没有这样做。
                      */
                      #ifndef MAX_LENGTH
                      #define MAX_LENGTH 15 //定义字符串最大长度
                      #endif

                      int MaxNum(int firstNum, int secondNum){
                          return firstNum > secondNum ? firstNum : secondNum;
                      }

                      //定义数组结构体
                      struct matrix{
                          int num;
                          int direct;
                      };

                      typedef matrix Matrix;

                      int LCS(char *strA, char *strB, int lengthA, int lengthB, Matrix *resultMatrix[]){
                          if (lengthA == 0 || lengthB == 0) {
                              return 0;
                          }
                          for (int i = 0; i &lt; lengthA; i++) {
                              for (int j = 0; j &lt; lengthB; j++) {
                                  resultMatrix[i][j].num = 0; //设置所有默认的最长为0
                                  resultMatrix[i][j].direct = 1; //所有默认方向变成上 0斜上，1上，-1左
                              }
                          }

                          for (int i = 0; i &lt; lengthA; i++) {
                              for (int j = 0; j &lt; lengthB; j++) {
                                  if (strA[i] == strB[j]) {
                                      resultMatrix[i+1][j+1].num = resultMatrix[i][j].num + 1;
                                      resultMatrix[i+1][j+1].direct = 0;
                                  }else{
                                      resultMatrix[i+1][j+1].num = MaxNum(resultMatrix[i+1][j].num, resultMatrix[i][j+1].num);
                                      resultMatrix[i+1][j+1].direct = resultMatrix[i+1][j].num > resultMatrix[i][j+1].num ? 1 : -1;
                                  }
                              }
                          }
                          return resultMatrix[lengthA][lengthB].num;
                      }

                      int main(int argc, const char * argv[]) {
                          char *strA = (char*)malloc(sizeof(char) * MAX_LENGTH);
                          char *strB = (char*)malloc(sizeof(char) * MAX_LENGTH);
                          scanf("%s",strA);
                          scanf("%s",strB);
                          int lengthA = (int)strlen(strA);
                          int lengthB = (int)strlen(strB);
                          Matrix *resultMatrix[lengthA+1];
                          for (int i = 0; i &lt;= lengthA; i++) {
                              resultMatrix[i] = (Matrix*)malloc(sizeof(struct matrix)* (lengthB+1));
                          }

                          int max = LCS(strA, strB, lengthA, lengthB, resultMatrix);
                          printf("%d\n",max);
                          std::cout &lt;&lt; "Hello, World!\n";
                          return 0;
                      }
 
                      </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Python:</div>
                    <pre class="language-javascript">
                        <code>
                            def find_lcsubstr(s1, s2): 
	                            m=[[0 for i in range(len(s2)+1)]  for j in range(len(s1)+1)]  #生成0矩阵，为方便后续计算，比字符串长度多了一列
	                            mmax=0   #最长匹配的长度
	                            p=0  #最长匹配对应在s1中的最后一位
	                            for i in range(len(s1)):
		                            for j in range(len(s2)):
			                            if s1[i]==s2[j]:
				                            m[i+1][j+1]=m[i][j]+1
				                            if m[i+1][j+1]>mmax:
					                            mmax=m[i+1][j+1]
					                            p=i+1
	                            return s1[p-mmax:p],mmax   #返回最长子串及其长度
 
                            print find_lcsubstr('abcdfg','abdfg')
                        </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Java:</div>
                    <pre class="language-javascript">
                      <code>
                        package DynamicPlan;
 
                        import java.util.Arrays;
 
                        public class MyComSub {
                            public static int ComSub(int [][]d,String s1,String s2){
                                char []a = s1.toCharArray();
                                char []b = s2.toCharArray();
                                int [][]c = new int[a.length + 1][b.length + 1];
                                for(int i = 1;i &lt;= a.length;i++){
                                    for(int j = 1;j &lt;= b.length;j++){
                                        //注意这里要减一，不然会超出数组长度错误
                                        if(a[i - 1] == b[j - 1]){
                                            c[i][j] = c[i - 1][j - 1] + 1;
                                            d[i][j] = 1;
                                        }
                                        else if(c[i - 1][j] >= c[i][j - 1]){
                                            c[i][j] = c[i - 1][j];
                                            d[i][j] = 3;
                                        }else{
                                            c[i][j] = c[i][j - 1];
                                            d[i][j] = 2;
                                        }
                                    }
                                }
                                return c[a.length][b.length];
                            }
                            //输出最长子序列
                            public static void Sub(int [][]d,String s1,int i,int j){
                            if(i == 0 || j ==0){
                                return;
                            }
                            //如果最优源来自左上方
                            if(d[i][j] == 1){
                                Sub(d,s1,i-1,j-1);
                                //注意要在这里输出，自己想想为什么
                                System.out.print(s1.charAt(i - 1));
                            //最优源来自最左边
                            }else if(d[i][j] == 2){
                                Sub(d,s1,i,j-1);
                            }{
                                //最优源来自上面
                                Sub(d, s1, i-1, j);
                            }
                            }
                        }
                      </code>
                    </pre>
                </div>
            </el-collapse-item>
        </el-collapse>
    </div>
</template>

<script lang="ts" setup>
import { ref } from 'vue'
const activeNames = ref(['thinking'])
const handleChange = (val: string[]) => {
    console.log(val)
}
// 代码实现部分
import "vue-code-highlight/themes/prism-solarizedlight.css";
import "vue-code-highlight/themes/window.css";

</script>

<style>
.image {
    width: 390px;
    border-radius: 10px;
    margin-right: 10px;
}
</style>